import Data.List

--we want a 20x20 matrix with all the coordinates having as value the number of paths that go through that point
--we only need to compute half of that matrix because it is symmetric
follows :: [Integer] -> [Integer]
follows row = rSum ++ [ last row * 2 + (2*(rSum !! (length rSum - 2))) ]
              where rSum = runningSum row

gridSequence = iterate follows
main = take 20 (gridSequence [1,2])


runningSum [] = []
runningSum all@(x:xs) = x : zipWith(+) (runningSum all) xs

-- the following finds all the routes (too long for anything > 10)
rowLength, colLength :: Integer
rowLength = 3
colLength = 3
next :: (Integer, Integer) -> [(Integer,Integer)] -> [(Integer,Integer)]
next sq@(x,y) path
     | x == rowLength && y == colLength = sq:path         --score!
     | otherwise = right ++ down
                   where right
                           | x == rowLength = []
                           | otherwise = (next (x+1,y) (sq:path))
                         down 
                           | y == colLength = []
                           | otherwise = (next (x,y+1) (sq:path))

--main = print $ toInteger (length (next (0,0) [])) `div` (rowLength * 2 + 1)
paths = next (0,0) []